Nhiệm Vụ Của Bạn 🎯
Kết nối lại $N$ hành tinh, được xác định bởi tọa độ 2D, bằng một mạng lưới "Hành Lang Siêu Tốc" với chi phí thấp nhất.
- Mục Tiêu:Kết nối tất cả $N$ hành tinh (đỉnh) sao cho chúng đều có thể truy cập được (trực tiếp hoặc gián tiếp).
- Mục Tiêu:Tìm ra thiết kế mạng lưới tối ưu nhằm giảm thiểu **tổng chi phí**.
Phân Tích 🛰️
Chi phí của một hành lang (cạnh) là khoảng cách Euclid:
$d = \sqrt{(x_1 - x_2)^2 + (y_1 - y_2)^2}$
- Một hành lang có thể được xây dựng giữa bất kỳhai hành tinh nào.
- Điều này có nghĩa là chúng ta có một đồ thị hoàn chỉnh (mật độ cao).
Giải Pháp ⚙️
Đây là một bài toán kinh điển về Cây khung nhỏ nhất (MST) vấn đề.
- Thuật Toán: Gợi ý đề xuất Thuật toán Prim (phiên bản $O(V^2)$), rất phù hợp với các đồ thị mật độ cao.
- Điểm Bắt Đầu: Chúng tôi sẽ bắt đầu thuật toán từ Hành tinh 0 để đảm bảo kết quả nhất quán.
Một đồ thị hoàn chỉnh (bên trái) chứa tất cả các cạnh khả dĩ. Cây khung nhỏ nhất (MST) (bên phải) là tập con cạnh rẻ nhất kết nối tất cả các đỉnh.